/*
 * Implement regular expression matching with support for '.' and '*'.
 *
 * '.' Matches any single character.
 * '*' Matches zero or more of the preceding element.
 *
 * The matching should cover the entire input string (not partial).
 *
 * The function prototype should be:
 * bool isMatch(const char *s, const char *p)
 *
 * Some examples:
 * isMatch("aa","a") --> false
 * isMatch("aa","aa") --> true
 * isMatch("aaa","aa") --> false
 * isMatch("aa", "a*") --> true
 * isMatch("aa", ".*") --> true
 * isMatch("ab", ".*") --> true
 * isMatch("aab", "c*a*b") --> true
 */
class Solution {
public:
    bool isMatch(const char *s, const char *p, int si, int pi) {
        if (!p[pi]) {
            return !s[si];
        }
        if (p[pi] == '*') {
            if (pi != 0) {
                bool res = isMatch(s, p, si, pi+1);
                if (res) {
                    return true;
                }
                if (p[pi-1] == '.' || p[pi-1] == s[si]) {
                    /* XXX: note s[si] */
                    res = s[si] && isMatch(s, p, si+1, pi);
                    if (res) {
                        return true;
                    }
                }
            }
            return false;
        } else if (p[pi] == '.') {
            if (p[pi+1] == '*') {
                return isMatch(s, p, si, pi+1);
            }
            /* XXX: note s[si] */
            return s[si] && isMatch(s, p, si+1, pi+1);
        } else {
            if (p[pi+1] == '*') {
                return isMatch(s, p, si, pi+1);
            }
            return p[pi] == s[si] && isMatch(s, p, si+1, pi+1);
        }
    }
    bool isMatch(const char *s, const char *p) {
        if (!s || !p) {
            return false;
        }
        return isMatch(s, p, 0, 0);
    }
};

int main() {
    return 0;
}
